package com.jjlin.chapter_1;

import java.util.*;
public class CD22{
    //书上的写法，较复杂
    public static int hanoiProblem(int num, String left, String mid, String right){
        if(num < 1)
            return 0;
        return process(num, left, mid, right, left, right);
    }

    public static int process(int num, String left, String mid, String right, String from, String to){
        if(num == 1){//base case
            if(from.equals(mid) || to.equals(mid)){
                System.out.println("Move 1 from " + from + " to " + to);
                return 1;
            }else{
                System.out.println("Move 1 from " + from + " to " + mid);
                System.out.println("Move 1 from " + mid + " to " + to);
                return 2;
            }
        }
        if(from.equals(mid) || to.equals(mid)){//起点或者终点中包括mid塔
            String another = (from.equals(left) || to.equals(left)) ? right : left;//获得辅助塔
            int part1 = process(num - 1, left, mid, right, from, another);
            int part2 = 1;
            System.out.println("Move " + num + " from " + from + " to " + another);
            int part3 = process(num - 1, left, mid, right, another, to);
            return part1 + part2 + part3;
        }else{//起点或者终点中都不包括mid塔
            int part1 = process(num - 1, left, mid, right, from, to);
            int part2 = 1;
            System.out.println("Move " + num + " from " + from + " to " + mid);
            int part3 = process(num - 1, left, mid, right, to, from);
            int part4 = 1;
            System.out.println("Move " + num + " from " + mid + " to " + to);
            int part5 = process(num - 1, left, mid, right, from, to);
            return part1 + part2 + part3 + part4 + part5;
        }

    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String left = "left";
        String mid = "mid";
        String right = "right";
        int stepCount = hanoiProblem(n, left, mid, right);
        System.out.println("It will move " + stepCount + " steps.");
    }
}


/*递归更简便的写法*/
/**
 * public class Main{
 *     public static int stepCount = 0;
 *     public static void hanoiProblem1(int num, String left, String mid, String right){
 *         if(num == 1){
 *              move(num, left, mid);
 *              move(num, mid, right);
 *         }else{
 *             hanoiProblem1(num - 1, left, mid, right);
 *             move(num, left, mid);
 *             hanoiProblem1(num - 1, right, mid, left);
 *             move(num, mid, right);
 *             hanoiProblem1(num - 1, left, mid, right);
 *         }
 *     }
 *
 *     public static void move(int num, String from, String to){
 *         System.out.println("Move " + num + " from " + from + " to " + to);
 *         stepCount++;
 *     }
 *
 *     public static void main(String[] args){
 *         Scanner sc = new Scanner(System.in);
 *         int n = sc.nextInt();
 *         String left = "left";
 *         String mid = "mid";
 *         String right = "right";
 *         hanoiProblem1(n, left, mid, right);
 *         System.out.println("It will move " + stepCount + " steps.");
 *     }
 * }
 */

//使用栈来求解汉诺塔问题
/**
 * import java.util.*;
 * public class Main{
 *
 *     public static enum Action{//使用枚举表示移动动作
 *         No, LToM, RToM, MToL, MToR;
 *     }
 *
 *     public static int hanoiProblem2(int num, String left, String mid, String right){
 *         Stack<Integer> lStack = new Stack<>();
 *         Stack<Integer> mStack = new Stack<>();
 *         Stack<Integer> rStack = new Stack<>();
 *         lStack.push(Integer.MAX_VALUE);//为了方便比较栈顶的塔，因此每个栈中都压入Integer.MAX_VALUE
 *         mStack.push(Integer.MAX_VALUE);
 *         rStack.push(Integer.MAX_VALUE);
 *         for(int i = num; i > 0; --i)
 *             lStack.push(i);
 *         Action[] pre = {Action.No};
 *         int step = 0;
 *         while(rStack.size() != num + 1){//由于之前压入了Integer.MAX_VALUE，因此这里是num + 1
 *             //第一个动作要保证是从lStack到mStack
 *             step += fStackTotStack(pre, Action.MToL, Action.LToM, lStack, mStack, left, mid);
 *             step += fStackTotStack(pre, Action.RToM, Action.MToR, mStack, rStack, mid, right);
 *             step += fStackTotStack(pre, Action.LToM, Action.MToL, mStack, lStack, mid, left);
 *             step += fStackTotStack(pre, Action.MToR, Action.RToM, rStack, mStack, right, mid);
 *         }
 *         return step;
 *     }
 *
 *     //pre记录之前的移动动作的相反动作，curAct是这次的移动动作，preAct是这次的移动动作的相反动作
 *     //这样主要是保证了不违反逆反原则
 *     public static int fStackTotStack(Action[] pre, Action preAct, Action curAct,
 *            Stack<Integer> fStack, Stack<Integer> tStack, String from, String to){
 *         if(pre[0] == curAct || fStack.peek() >= tStack.peek())//判断是否违反小压大和逆反原则
 *             return 0;
 *         else{
 *             pre[0] = preAct;
 *             tStack.push(fStack.pop());
 *             System.out.println("Move " + tStack.peek() + " from " + from + " to " + to);
 *             return 1;
 *         }
 *     }
 *
 *     public static void main(String[] args){
 *         Scanner sc = new Scanner(System.in);
 *         int n = sc.nextInt();
 *         String left = "left";
 *         String mid = "mid";
 *         String right = "right";
 *         System.out.println("It will move " + hanoiProblem2(n, left, mid, right) + " steps.");
 *     }
 * }
 */
